Search results for " Turing"

Positive Versions of Polynomial Time

1998

Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.

Intelligenza artificiale

2009

Weakly nonlinear analysis of Turing patterns in a morphochemical model for metal growth

2015

We focus on the morphochemical reaction–diffusion model introduced in Bozzini et al. (2013) and carry out a nonlinear bifurcation analysis with the aim to characterize the shape and the amplitude of the patterns arising as the result of Turing instability of the physically relevant equilibrium. We perform a weakly nonlinear multiple scales analysis, and derive the normal form equations governing the amplitude of the patterns. These amplitude equations allow us to construct relevant solutions of the model equations and reveal the presence of multiple branches of stable solutions arising as the result of subcritical bifurcations. Hysteretic type phenomena are highlighted also through numerica…

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

Vita, morte e miracoli di Alan Mathison Turing

2007

La vita di Turing si puo leggere in molte biografie: ottima ed enciclopedica quella di Andrew Hodges (pubblicata in Italia da Bollati Boringhieri); molto piacevole l’agile libretto di Gianni Rigamonti, Turing, il genio e lo scandalo (Flaccovio editore, Palermo, 1991). In entrambi i libri si possono anche trovare cenni alla sua tragica fine, della quale la societa inglese di quel tempo non puo certo menar vanto; ma chissa come si sarebbero comportate altre societa.

Super-critical and sub-critical bifurcations in a reaction-diffusion Schnakenberg model with linear cross-diffusion

2016

In this paper the Turing pattern formation mechanism of a two components reaction-diffusion system modeling the Schnakenberg chemical reaction is considered. In Ref. (Madzavamuse et al., J Math Biol 70(4):709–743, 2015) it was shown how the presence of linear cross-diffusion terms favors the destabilization of the constant steady state. We perform the weakly nonlinear multiple scales analysis to derive the equations for the amplitude of the Turing patterns and to show how the cross-diffusion coefficients influence the occurrence of super-critical or sub-critical bifurcations. We present a numerical exploration of far from equilibrium regimes and prove the existence of multistable stationary…

One-Counter Verifiers for Decidable Languages

2013

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…

Chemical self-organization in self-assembling biomimetic systems

2009

Abstract Far-from-equillibrium oscillating chemical reactions are among the simplest systems showing complex behaviors and emergent properties. This class of reactions is often employed to mimic and understand the mechanisms of a great variety of biological processes. In this context, pattern formation due to the coupling between reaction and transport phenomena represent an active and promising research area. In this paper, we present results coming from experiments where we tried to blend the structural properties of self-assembled matrixes (sodium dodecyl sulphate micelles and phospholipid bilayers) together with the evolutive peculiarities of the Belousov–Zhabotinsky reaction. A series …

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

Io Robot, la (fanta)scienza e le altre

2009

Presentazione in termini accessibili a un vasto pubblico di alcuni problemi centrali della robotica, l'intelligenza atificiale, la teoria della calcolabilità con cenni alla vita di A. M. Turing.